import sys
import nltk
parse_table=[]
production_list=[]
production_count=0

def ckyparse(tagged_list,grammar):

    global production_count
    global parse_table
    global production_list

    production_count=0
    parse_table=[]
    production_list=[]
    
    ques_tag_pattern=""
    
    for i in tagged_list:
        ques_tag_pattern+=i[1]
        ques_tag_pattern+=" "

    ques_pattern=""
    
    for i in tagged_list:
        ques_pattern+=i[0]
        ques_pattern+=" "
    
    ques_list=ques_pattern.split()  
    ques_tag_list=ques_tag_pattern.split()
    length=len(ques_tag_list)
    
    #print ques_tag_list
    #raw_input()

    #initialize the parse_table
    for i in range(length+1):
        ml=[]
        for j in range(length+1):
            ml.append(-1)
        parse_table.append(ml)

    #first forloop of cky algorithm        
    for j in range(1,length+1):
        #table[j-1,j]<-{A|A -> words[j] E grammar
        parse_table[j-1][j]=[]
        production_list.append([{ques_tag_list[j-1]:ques_list[j-1]},[-1,-1]])
        parse_table[j-1][j].append(production_count)
        production_count+=1

        add_productions(parse_table[j-1][j],production_list[production_count-1],[production_count-1,-1],grammar)
    
        #print "curr prod list= ",curr_production_list
        #raw_input()

    
        #second forloop of cky algorithm
        for i in range(j-2,-1,-1):
            parse_table[i][j]=[]
        
            #third forloop of cky algorithm
            for k in range(i+1,j):
                blist=parse_table[i][k]
                clist=parse_table[k][j]
                B=[]
                C=[]
                for tmp in blist:
                    B.append({production_list[tmp][0].keys()[0]:tmp})

                for tmp in clist:                    
                    C.append({production_list[tmp][0].keys()[0]:tmp})

                for tmp in B:
                    for tmp1 in C:
                        key=tmp.keys()[0]
                        key1=tmp1.keys()[0]
            
                        two_val=[key,key1]
                        l=get_right_productions(two_val,grammar)
                        for tmp3 in l:
                            add_this_rule={tmp3:two_val}
                            production_list.append([add_this_rule,[tmp[key],tmp1[key1]]])
                            parse_table[i][j].append(production_count)
                            production_count+=1
                            add_productions(parse_table[i][j],production_list[production_count-1],[production_count-1,-1],grammar)
    
        
    return [parse_table,production_list]


def add_productions(p_table_cell,production,offset,grammar):
    """ to do
    """
    to_check_production_lhs=production[0].keys()[0]
    to_check_production_rhs=production[0][to_check_production_lhs]
    global production_count
    
    for i in grammar:
        lhs=i.keys()[0]
        rhs=i[lhs]
        for j in rhs:
            if j==[to_check_production_lhs]:
                add_this_rule={lhs:j}
                production_list.append([add_this_rule,offset])
                p_table_cell.append(production_count)
                production_count+=1

                #call recursively
                add_productions(p_table_cell,production_list[production_count-1],[production_count-1,-1],grammar)
    return


def get_right_productions(rhslist,grammar):
    """ Returns 1 if A -> rhslist is present in the grammar..
    else, return 0.
    """
    ret_list=[]                                       
    for i in rhslist:
        if i== -1:
            return ret_list

    for i in grammar:
        lhs=i.keys()[0]
        rhs=i[lhs]
        for j in rhs:
            if j== rhslist:
                ret_list.append(lhs)

    return ret_list
def get_parse_trees(ptable,plist):
	"""returns the parse trees according to the parse_table, and plist
	"""
	p=ptable[0]
	p.reverse()
	for i in p:
		if i!=[]:
			parse=i[0]
			tree=[]
			app_nod1=parse
			app_nod2=-1
			rec_tree(tree,app_nod1,app_nod2,plist)
			break		
	
	return tree
	
def rec_tree(tree,app_nod1,app_nod2,plist):
	if app_nod1==-1 and app_nod2==-1:
		return
	
	if app_nod1!=-1:
		tree.append(plist[app_nod1][0])
		new_app_nod2=plist[app_nod1][1][1]
		new_app_nod1=plist[app_nod1][1][0]
		rec_tree(tree,new_app_nod1,new_app_nod2,plist)
	
	if app_nod2!=-1:
		tree.append(plist[app_nod2][0])
		new_app_nod1=plist[app_nod2][1][0]
		new_app_nod2=plist[app_nod2][1][1]
		rec_tree(tree,new_app_nod1,new_app_nod2,plist)
	
	return

def gen_grammar(filename):
        ip=open('E:\project\\aqas\grammar\grammar.cfg',"r")
        flag=0
        grammar=[]
        g_dict={}
        while True:
                lin=ip.readline()
                if lin=="":
                        break
                else:
                        words=lin.split()
                        if flag==0:
                                g_dict[words[0]]=[]
                        if words!=[]:
                                flag=1
                                tmp=words[2:]
                                g_dict[words[0]].append(tmp)
                        else:
                                grammar.append(g_dict)
                                g_dict={}
                                flag=0
        return grammar

def test_parse(t):
	g=gen_grammar('')
	toks=nltk.word_tokenize(t)
	tags=nltk.pos_tag(toks)
	ptable,plist=ckyparse(tags,g)
	#tree=get_parse_trees(ptable,plist)
	#print tree
	count=0
	for i in plist:
		print count,i,"\n"
		count+=1
		
	tree=get_parse_trees(ptable,plist)
	print tree